#include <stdio.h>
#include <stdlib.h>

#define kMaxSize 1000001
#define NIL -1

typedef int Position;
typedef struct StringNode *String;
struct StringNode {
    char data[kMaxSize]; /* 存储字符的数组 */
    int length; /* 字符串长度 */
};

String InitStr() {
    /* 初始化一个空的字符串 */
    String s;

    s = (String)malloc(sizeof(struct StringNode));
    s->length = 0;

    return s;
}

Position MapChar(char c) {
    /* 将字符c转换为0~kMaxSize-1内的整数 */
    return (c % kMaxSize);
}

/* 算法4-16：字符串模式匹配的Sunday算法  PatternMatchSunday(s,t) */
Position PatternMatchSunday(String s, String t) {
    int n, m, i, j;
    Position p, idx;
    int shift[kMaxSize];

    n = s->length;
    m = t->length;
    p = NIL;
    for (i = 0; i < kMaxSize; i++) { /* 初始化shift */
        shift[i] = m + 1;
    }
    for (i = 0; i < m; i++) {
        /* 将t中字符映射成0~kMaxSize-1中整数 */
        idx = MapChar(t->data[i]);
        shift[idx] = m - i; /* 即t.data[i]的偏移量 */
    }
    i = 0;
    while (i <= (n - m)) {
        j = 0;
        while ((j < m) && (s->data[i + j] == t->data[j])) {
            j++;
        }
        if (j == m) { /* 匹配成功 */
            p = i;
            break;
        } else {
            idx = MapChar(s->data[i + m]);
            i += shift[idx]; /* 右移i */
        }
    }
    return p;
}
/* 算法4-16 结束 */

String ReadString() {
    int i;
    String s;

    s = InitStr(); /* 创建空的字符串 */
    i = 0;
    s->data[i] = getchar();
    while (s->data[i] != '\n') {
        i++;
        s->data[i] = getchar();
    }
    s->data[i] = '\0'; /* 字符串结束符占1位 */
    s->length = i;
    return s;
}

int main(void) {
    String s, t;
    Position p;

    s = ReadString();
    t = ReadString();
    p = PatternMatchSunday(s, t);
    if (p != NIL)
        printf("%s\n", s->data + p);
    else
        printf("匹配失败。\n");

    return 0;
}